package com.github.hgkmail.hello.leetcode101.pointer.tree;

import com.github.hgkmail.hello.leetcode101.base.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class LC112PathSum {
    public void dfs(TreeNode node, int currSum, List<Boolean> find) {
        if (node==null || !find.isEmpty()) {
            return;
        }
        if (node.val==currSum && node.left==null && node.right==null) {
            find.add(Boolean.TRUE);
            return;
        }
        dfs(node.left, currSum-node.val, find);
        dfs(node.right, currSum-node.val, find);
    }

    public boolean hasPathSum(TreeNode root, int targetSum) {
        List<Boolean> find = new ArrayList<>();
        dfs(root, targetSum, find);

        return !find.isEmpty();
    }

    public static void main(String[] args) {

    }
}
